package leetcode.hot100;

import datastruct.tree.TreeNode;

import java.util.HashMap;

public class Solution105 {

    /**
     * 根据一棵树的前序遍历与中序遍历构造二叉树。
     * 从子序列构建左右子树，在中序中查找根节点位置
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        if(n==0) return null;
        //构建Hash表，快速定位root在inorder位置
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(inorder[i],i);
        }
        return buildSubTree(preorder,inorder,0,n-1,0,n-1,map);
    }

    public TreeNode buildSubTree(int[] preorder, int[] inorder, int preorderStart, int preorderEnd,
                                 int inorderStart, int inorderend, HashMap<Integer,Integer> map) {
        //根据preorder[preorderStart:preorderEnd]和inorder[inorderStart:inorderend]构建子树
        if(preorderStart==preorderEnd) return new TreeNode(preorder[preorderStart]);
        //preorder[preorderStart]就是根节点，它后面开始直到preorderEnd都是这棵树的节点
        TreeNode root = new TreeNode(preorder[preorderStart]);
        //首先要查找根节点在inorder[inorderStart:inorderend]的位置，确定左右子树
        int rootIdxOfInorder = map.get(root.val);
//        int rootIdxOfInorder = inorderStart;
//        while (rootIdxOfInorder<=inorderend&&inorder[rootIdxOfInorder]!=root.val) rootIdxOfInorder++;
        //root在中序遍历开始，说明没有左子树
        if(rootIdxOfInorder==inorderStart) root.left = null;
        else root.left = buildSubTree(preorder,inorder,
                preorderStart+1,preorderStart+rootIdxOfInorder-inorderStart,
                inorderStart,rootIdxOfInorder-1,map);
        //root在中序遍历结束，说明没有右子树
        if(rootIdxOfInorder==inorderend) root.right = null;
        else root.right = buildSubTree(preorder,inorder,
                preorderStart+rootIdxOfInorder-inorderStart+1,preorderEnd,
                rootIdxOfInorder+1,inorderend,map);
        return root;
    }
}
